﻿using System;
using System.Collections.Generic;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Problems.Traversals;
using Algoritmia.Utils;

namespace Algoritmia.Problems.SpanningTrees.GraphTraversal
{
    public class GraphTraversalSpanningTreeFinder<T> : ISpanningTreeFinder<T>
    {
        private readonly Func<IDigraph<T>, IGraphBreadthFirstTraverser<T, Tuple<T, T>>> _createTraverser;
        private readonly EqualityComparison<T> _equalityComparison;

        public GraphTraversalSpanningTreeFinder(EqualityComparison<T> equalityComparison = null,
            Func<IDigraph<T>,IGraphBreadthFirstTraverser<T,Tuple<T,T>>> createTraverser = null)
        {
            _createTraverser = createTraverser ?? (g => new BreadthFirstTraverser<T, Tuple<T, T>>());
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
        }

        public IEnumerable<Tuple<T, T>> SpanningTree(IDigraph<T> g, T source)
        {
            var traverser = _createTraverser(g);
            foreach(var tuple in traverser.Traverse(g,source,(u,v) => new Tuple<T, T>(u,v)))
            {
                if (!_equalityComparison(tuple.Item1,tuple.Item2))
                    yield return tuple;
            }
        }
    }
}
